package com.isaiah.map;

/**
 * @Title: 基于二分搜索树的Map实现
 * @Description: ${todo}
 * @author: Haijun
 * @emial: isaiah@sohu.com
 * @date 2020/5/2513:37
 */
public class BSTreeMap<K extends Comparable<K>, V> implements Map<K, V> {


    /**
     * 定义节点类型
     */
    private class Node{
        private K key;
        private V value;
        private Node left;
        private Node right;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
            this.left = null;
            this.right = null;
        }

        public Node() {
        }
    }
    /** 根节点 */
    private Node root;

    /** 实际元素个数 */
    private int size;

    public BSTreeMap() {
        this.root = null;
        this.size = 0;
    }

    @Override
    public void add(K key, V value) {
        root = this.add(root, key, value);
    }

    private Node add(Node node, K key, V value) {
        // 如果node为空，当前新创建的节点就是根节点
        if (node == null){
            this.size ++;
            return new Node(key, value);
        }
        // 如果要添加的key小于当前node，则在左子树添加
        if (key.compareTo(node.key) < 0){
            node.left = add(node.left, key, value);
        }
        // 如果要添加的key大于当当前node，则在右子树添加
        else if(key.compareTo(node.key) > 0){
            node.right = add(node.right, key, value);
        }
        // 如果要添加的key等于当当前node，则更新value
        else{
            node.value = value;
        }
        return node;

    }

    @Override
    public V remove(K key) {
        // 1. 查找到要删除的元素
        Node node = getNode(root, key);
        if (node != null){
            //2. 删除
            root = remove(root, key);
            return node.value;
        }
        return null;
    }

    private Node remove(Node node, K key){
        if (node == null){
            return null;
        }
        // 要删除的节点key小于node节点的key，则要删除节点在node为根的左子树
        if (key.compareTo(node.key) < 0){
            node.left = remove(node.left, key);
            return node;
        }
        // 要删除的节点key大于node节点的key，则要删除节点在node为根的右子树
        else if (key.compareTo(node.key) > 0){
            node.right = remove(node.right, key);
            return node;
        }
        // 要删除的节点key等于node节点的key，则要删除节点正好就是node节点
        else{       //key.compareTo(node.key) == 0

            // 要删除的节点左子树为null的情况
            if (node.left == null){
                Node rightNode = node.right;
                node.right = null;
                size --;
                return rightNode;
            }

            // 要删除的节点右子树为null的情况
            if (node.right == null){
                Node leftNode = node.left;
                node.left = null;
                size --;
                return leftNode;
            }

            /** Hibbard 删除逻辑 */
            // 1. 找到比待删除元素大的最小节点：即待删除节点右子树中最小节点
            Node successor = mininum(node.right);
            // 2. 让待删除节点右子树中最小节点right指向删除节点右子树中最小节点后的子树
            successor.right = removeMin(node.right);
            // 3. 让待删除节点右子树中最小节点left指向原来left
            successor.left = node.left;
            // 4. 删除节点
            node.left = node.right = null;
            return successor;
        }

    }

    private Node mininum(Node node) {
        if (node.left == null){
            return node;
        }
        return mininum(node.left);
    }

    /**
     * 删除二分搜索树的最小元素
     * @return
     */
    public Node removeMin(){
        // 找到最小元素
        return null;
    }

    private Node removeMin(Node node) {
        if (node.left == null){
            // 当前节点可能有右孩子
            Node rightNode = node.right;
            // 把要删除的node的右孩子置为null
            node.right = null;
            size--;
            return rightNode;
        }
        node.left = removeMin(node.left);
        return node;
    }


    @Override
    public boolean contains(K key) {
        return getNode(root, key) != null;
    }

    @Override
    public V get(K key) {
        // 1. 根据key找到Node
        Node node = this.getNode(root, key);
        // 2. 返回node中的value
        return node == null ? null : node.value;
    }

    private Node getNode(Node node, K key) {
        if(node == null){
            return null;
        }

        // 如果要查找的key等于node的key，哪么node就是要查找的节点
        if (key.compareTo(node.key) == 0){
            return node;
        }
        // 如果要查找的key小于node的key，哪么要查找的节点在node的左子树
        else if (key.compareTo(node.key) < 0){
            return getNode(node.left, key);
        }
        // 如果要查找的key大于node的key，哪么要查找的节点在node的右子树
        else{ //(key.compareTo(node.key) > 0)
            return getNode(node.right, key);
        }

    }


    @Override
    public void set(K key, V newValue) {
        // 1. 根据key查找节点
        Node node = getNode(root, key);
        if(node == null){
            throw new IllegalArgumentException(key + " doesn't exist!");
        }

        // 2. 更新节点值
        node.value = newValue;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }
}
